//
//enum Color { RED, BLACK };
//
//template<class K, class V>
//struct RBTreeNode
//{
//    RBTreeNode<K, V>* _left;
//    RBTreeNode<K, V>* _right;
//    RBTreeNode<K, V>* _parent;
//    pair<K, V> _kv;
//    Color _col;
//
//    RBTreeNode(const pair<K, V>& kv)
//        :_left(nullptr)
//         ,_right(nullptr)
//         ,_parent(nullptr)
//         ,_kv(kv)
//    {}
//};
//
//template<class K, class V>
//class RBTree 
//{
//    typedef RBTreeNode<K, V> Node;
//public:
//    bool insert(const pair<K, V>& kv)
//    {
//        if (_root == nullptr) 
//        {
//            _root = new Node(kv);
//            _root->_col = BLACK;
//            return true;
//        }
//
//        Node* cur = _root;
//        Node* parent = nullptr;
//
//        while (cur)
//        {
//            if (cur->_kv.first < kv.first)
//            {
//                parent = cur;
//                cur = cur->_right;
//            }
//            else if (cur->_kv.first > kv.first)
//            {
//                parent = cur;
//                cur = cur->_left;
//            }
//            else 
//            {
//                return false;
//            }
//        }
//
//        cur = new Node(kv);
//        cur->_col = RED;
//        if (parent->_kv.first < kv.first)
//            parent->_right = cur;
//        else 
//            parent->_left = cur;
//        cur->_parent = parent;
//
//        while (parent && parent->_col == RED)
//        {
//            Node* grandfather = parent->_parent;
//            assert(grandfather && grandfather->_col == BLACK);
//
//            if (grandfather->_left == parent)
//            {
//                Node* uncle = grandfather->_right;
//                if (uncle && uncle->_col == RED)
//                {
//                    parent->_col = uncle->_col = BLACK;
//                    grandfather->_col = RED;
//                    cur = grandfather;
//                    parent = cur->_parent;
//                }
//                else 
//                {
//                    if (parent->_left == cur)
//                    {
//                        RotateR(grandfather);
//                        parent->_col = BLACK;
//                        grandfather->_col = RED;
//                    }
//                    else 
//                    {
//                        RotateL(parent);
//                        RotateR(grandfather);
//                        cur->_col = BLACK;
//                        grandfather->_col = RED;
//                    }
//                    break;
//                }
//            }
//            else 
//            {
//                Node* uncle = grandfather->_left;
//                if (uncle && uncle->_col == RED)
//                {
//                    parent->_col = uncle->_col = BLACK;
//                    grandfather->_col = RED;
//                    cur = grandfather;
//                    parent = cur->_parent;
//                }
//                else 
//                {
//                    if (parent->_right == cur)
//                    {
//                        RotateL(grandfather);
//                        parent->_col = BLACK;
//                        grandfather->_col = RED;
//                    }
//                    else 
//                    {
//                        RotateR(parent);
//                        RotateL(grandfather);
//                        cur->_col = BLACK;
//                        grandfather->_col = RED;
//                    }
//                    break;
//                }
//            }
//        }
//
//        _root->_col = BLACK;
//        return true;
//    }
//
//    ~RBTree() { _Destroy(_root); _root = nullptr; }
//    void InOrder() { _InOrder(_root); }
//    
//    bool isRBTree()
//    {
//        if (_root == nullptr)
//            return true;
//        if (_root->_col != BLACK)
//            return false;
//
//        int benchmake = 0;
//        return _isRBTree(_root, 0, benchmake);
//    }
//
//private:
//
//    void RotateL(Node* parent)
//    {
//        Node* sub = parent->_right;
//        Node* subL = sub->_left;
//
//        parent->_right = subL;
//        if (subL)
//            subL->_parent = parent;
//
//        Node* ppNode = parent->_parent;
//        sub->_left = parent;
//        parent->_parent = sub;
//
//        if (parent == _root)
//        {
//            _root = sub;
//            sub->_parent = nullptr;
//        }
//        else 
//        {
//            if (ppNode->_left == parent)
//                ppNode->_left = sub;
//            else 
//                ppNode->_right = sub;
//            sub->_parent = ppNode;
//        }
//    }
//
//    void RotateR(Node* parent)
//    {
//        Node* sub = parent->_left;
//        Node* subR = sub->_right;
//
//        parent->_left = subR;
//        if (subR)
//            subR->_parent = parent;
//
//        Node* ppNode = parent->_parent;
//        sub->_right = parent;
//        parent->_parent = sub;
//
//        if (parent == _root)
//        {
//            _root = sub;
//            sub->_parent = nullptr;
//        }
//        else 
//        {
//            if (ppNode->_left == parent)
//                ppNode->_left = sub;
//            else 
//                ppNode->_right = sub;
//            sub->_parent = ppNode;
//        }
//    }
//
//    bool _isRBTree(Node* root, int blacknum, int& benchmake)
//    {
//        if (root == nullptr)
//        {
//            if (benchmake == 0)
//                benchmake = blacknum;
//            if (benchmake != blacknum)
//                return false;
//            return true;
//        }
//
//        if (root->_col == BLACK)
//            blacknum ++ ;
//        if (root->_col == RED && root->_parent->_col == RED)
//        {
//            cout << "出现连续的红色节点~错误!" << endl;
//            return false;
//        }
//
//        return _isRBTree(root->_left, blacknum, benchmake)
//            && _isRBTree(root->_right, blacknum, benchmake);
//    }
//
//    void _InOrder(Node* root)
//    {
//        if (root == nullptr)
//            return;
//
//        _InOrder(root->_left);
//        cout << root->_kv.first << ':' << root->_kv.second << endl;
//        _InOrder(root->_right);
//    }
//
//    void _Destroy(Node* root)
//    {
//        if (root == nullptr)
//            return;
//
//        _Destroy(root->_left);
//        _Destroy(root->_right);
//        delete root;
//    }
//
//private:
//    Node* _root = nullptr;
//};


enum Color { RED, BLACK };

template<class T>
struct RBTreeNode
{
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    T _data;
    Color _col;

    RBTreeNode(const T& data)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(data)
    {}
};

template<class T, class Ref, class Ptr>
struct __RBTreeIterator 
{
    typedef RBTreeNode<T> Node;
    typedef __RBTreeIterator<T, Ref, Ptr> Self;

    Node* _node;

    __RBTreeIterator(Node* node) :_node(node) {}

    bool operator==(const Self& s) { return _node == s._node; }
    bool operator!=(const Self& s) { return _node != s._node; }

    Ref operator*() { return _node->_data; }
    Ptr operator->() { return &_node->_data; }

    Self& operator++()
    {
        if (_node->_right)
        {
            Node* left = _node->_right;
            while (left->_left)
                left = left->_left;
            _node = left;
        }
        else 
        {
            Node* parent = _node->_parent;
            Node* cur = _node;
            while (parent && parent->_right == cur)
            {
                parent = parent->_parent;
                cur = cur->_parent;
            }
            _node = parent;
        }
        return *this;
    }
    Self operator++(int)
    {
        Self tmp(_node);
        ++ (*this);
        return tmp;
    }

    Self& operator--()
    {
        if (_node->_left)
        {
            Node* right = _node->_left;
            while (right->_right)
                right = right->_right;
            _node = right;
        }
        else 
        {
            Node* parent = _node->_parent;
            Node* cur = _node;
            while (parent && parent->_left == cur)
            {
                parent = parent->_parent;
                cur = cur->_parent;
            }
            _node = parent;
        }
        return *this;
    }
    Self operator--(int)
    {
        Self tmp(_node);
        -- (*this);
        return tmp;
    }

    Self operator+(int k)
    {
        Self tmp(_node);
        while (k -- )
            ++ tmp;
        return tmp;
    }
    Self operator-(int k)
    {
        Self tmp(_node);
        while (k -- )
            -- tmp;
        return tmp;
    }
};

template<class K, class T, class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    typedef __RBTreeIterator<T, T&, T*> iterator;

    iterator begin()
    {
        Node* cur = _root;
        while (cur && cur->_left)
            cur = cur->_left;
        return iterator(cur);
    }
    iterator end() { return iterator(nullptr); }

    pair<iterator, bool> insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root), true);
        }
        
        KeyOfT kf;
        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (kf(cur->_data) < kf(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kf(cur->_data) > kf(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return make_pair(cur, false);
            }
        }

        cur = new Node(data);
        cur->_col = RED;
        if (kf(parent->_data) < kf(data))
            parent->_right = cur;
        else
            parent->_left = cur;
        cur->_parent = parent;
        Node* newnode = cur;

        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            assert(grandfather && grandfather->_col == BLACK);

            if (grandfather->_left == parent)
            {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if (parent->_left == cur)
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if (parent->_right == cur)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }

        _root->_col = BLACK;
        return make_pair(iterator(newnode), true);
    }

    ~RBTree() { _Destroy(_root); _root = nullptr; }
    void InOrder() { _InOrder(_root); }

    bool isRBTree()
    {
        if (_root == nullptr)
            return true;
        if (_root->_col != BLACK)
            return false;

        int benchmake = 0;
        return _isRBTree(_root, 0, benchmake);
    }

private:

    void RotateL(Node* parent)
    {
        Node* sub = parent->_right;
        Node* subL = sub->_left;

        parent->_right = subL;
        if (subL)
            subL->_parent = parent;

        Node* ppNode = parent->_parent;
        sub->_left = parent;
        parent->_parent = sub;

        if (parent == _root)
        {
            _root = sub;
            sub->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = sub;
            else
                ppNode->_right = sub;
            sub->_parent = ppNode;
        }
    }

    void RotateR(Node* parent)
    {
        Node* sub = parent->_left;
        Node* subR = sub->_right;

        parent->_left = subR;
        if (subR)
            subR->_parent = parent;

        Node* ppNode = parent->_parent;
        sub->_right = parent;
        parent->_parent = sub;

        if (parent == _root)
        {
            _root = sub;
            sub->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = sub;
            else
                ppNode->_right = sub;
            sub->_parent = ppNode;
        }
    }

    bool _isRBTree(Node* root, int blacknum, int& benchmake)
    {
        if (root == nullptr)
        {
            if (benchmake == 0)
                benchmake = blacknum;
            if (benchmake != blacknum)
                return false;
            return true;
        }

        if (root->_col == BLACK)
            blacknum++;
        if (root->_col == RED && root->_parent->_col == RED)
        {
            cout << "出现连续的红色节点~错误!" << endl;
            return false;
        }

        return _isRBTree(root->_left, blacknum, benchmake)
            && _isRBTree(root->_right, blacknum, benchmake);
    }

    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_kv.first << ':' << root->_kv.second << endl;
        _InOrder(root->_right);
    }

    void _Destroy(Node* root)
    {
        if (root == nullptr)
            return;

        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }

private:
    Node* _root = nullptr;
};
